package com.li.list;

public class 合并两个排序的链表 {
	public static void main(String[] args) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		node1.next = node3;
		
		node3.next = node5;
		
		node2.next = node4;
		node4.next = node6;
		
		printList(mergeList(node1, node2));
	}
	
	/**
	 * 打印链表
	 * @param head
	 */
	public static void printList(Node head){
		while((head = head.next)!=null){
			System.out.print(head.value+" ");
		}
		System.out.println();
	}
	public static  Node mergeList(Node list1,Node list2) {
        //新建一个头节点，用来存合并的链表。
        Node head=new Node();
        head.next=null;
        Node root=head;
        while(list1!=null&&list2!=null){
            if(list1.value<list2.value){
                head.next=list1;
                head=list1;
                list1=list1.next;
            }else{
                head.next=list2;
                head=list2;
                list2=list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(list1!=null){
            head.next=list1;
        }
        if(list2!=null){
            head.next=list2;
        }
        return root;
    }
}
